package com.guan.mysolutionstudy;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * @ClassName LongestPalindromic
 * @Author GuanCary
 * @Date 2020/5/12 20:31
 * @Version 1.0
 * LeetCode:  给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。
 * 比如`"Aa"`不能当做一个回文字符串。注意:假设字符串的长度不会超过 1010。
 * 回文串：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
 * 输入:
 * "abccccdd"
 * 输出:
 * 7
 * 解释:
 * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。//b字符丢掉
 * 思路
 * 我们上面已经知道了什么是回文串？现在我们考虑一下可以构成回文串的两种情况：
 * <p>
 * - 字符出现次数为双数的组合
 * - 字符出现次数为双数的组合+一个只出现一次的字符
 * <p>
 * 统计字符出现的次数即可，双数才能构成回文。因为允许中间一个数单独出现，比如“abcba”，所以如果最后有字母落单，总长度可以加
 * 1。首先将字符串转变为字符数组。然后遍历该数组，判断对应字符是否在hashset中，如果不在就加进去，如果在就让count++，
 * 然后移除该字符！并添加到字符到hashSet中,这样就能找到出现次数为双数的字符个数。//想获得这个字符,可以添加到一个动态字符串里
 * 最后查看这个HashSet是否为1或者0,如果是的话就
 **/
public class LongestPalindromic {
    public String solution(String str) {
        //HashSet自动筛选出独立的元素,不能重复
        HashSet hashSet = new HashSet();
        ArrayList<Character> characters = new ArrayList<Character>();
        //记录位数
        int count = 0;
        //首先将传入的字符串转化为字符数组
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (!hashSet.contains(chars[i])) {
                System.out.println("字符" + chars[i] + "添加成功!");
                characters.add(chars[i]);
                hashSet.add(chars[i]);
            } else {
                //添加到动态数组
                characters.add(chars[i]);
                count++;
                //将该字符在HashSet中移除
                hashSet.remove(chars[i]);
            }
        }
        System.out.println(characters.toString());
        //输入位数三目运算符表达式
        count = hashSet.isEmpty() ? count * 2 : count * 2 + 1;
        System.out.println("最多可以为" + count + "位的回文字符串");
        return characters.toString();
    }

    @Test
    public void Test() {
        solution("abcbcd");
        solution("abccccdd");
        solution("cacacaca");
        solution("aAaaaa");
    }
}